#include "project2.h"
#include <iostream>
#include <time.h>
#include <stdlib.h>
using namespace std;

void BaselineMergeSort(int* dataArray, int sizeOfDataArray) 
{	    
    //One elem doesn't need sorting.
    if (sizeOfDataArray > 1) 
    {	
        int* oneArr = new int[sizeOfDataArray/2];
        int* twoArr = new int[sizeOfDataArray/2];
        int counter = 0;
        // copy a to b
        for (int i = 0; i < sizeOfDataArray / 2; i++) 
        {
            oneArr[i] = dataArray[i];
        }
        // copy a to c
        for (int i = 0, j = sizeOfDataArray / 2; j < sizeOfDataArray - 1; i++, j++) 
        {
            twoArr[i] = dataArray[j];
        }
        BaselineMergeSort(oneArr, sizeOfDataArray/2);
        BaselineMergeSort(twoArr, sizeOfDataArray/2);
        BaselineMerge(oneArr, sizeOfDataArray / 2, twoArr, sizeOfDataArray - (sizeOfDataArray / 2), dataArray);
        delete oneArr;
        delete twoArr;
    }
}



void BaselineMerge(int* left, int sizeOfLeft, int* right, int sizeOfRight, int* result)
{
    int leftCounter, rightCounter, mergeCounter;
    leftCounter = 0;
    rightCounter = 0;
    mergeCounter = 0;
    // merge the two arrays
    while ((leftCounter < sizeOfLeft) && (rightCounter < sizeOfRight))
    {
        if(left[leftCounter] <= right[rightCounter])
        {
            result[mergeCounter] = right[rightCounter];
            rightCounter++;
        }
        else
        {
            result[mergeCounter] = left[leftCounter];
            leftCounter++;
        }
        mergeCounter++;
    }

    // handle the left-overs

    // if the entire left was used, then we have left-overs from the right to copy over
    if(leftCounter == sizeOfLeft)
    {
        // copy the right to the result
        while(rightCounter < sizeOfRight)
        {
            result[mergeCounter] = right[rightCounter];
            mergeCounter++;
            rightCounter++;
        }        
    }
    else
    {
        // copy the left to the result
        while(leftCounter < sizeOfLeft)
        {
            result[mergeCounter] = left[leftCounter];
            mergeCounter++;
            leftCounter++;
        }
    }
}

void __fastcall OptMergeSort(int& data, int size)
{
    //One elem doesn't need sorting.
    if (size > 1) 
    {	
        int halfsize = size / 2;
        int* oneArr = new int[halfsize];
        int* twoArr = new int[halfsize];
        int counter = 0;        
        // copy a to b
        for (int i = 0; i < halfsize; i++) 
        {
            oneArr[i] = (&data)[i];
        }
        // copy a to c
        for (int i = 0, j = halfsize; j < size - 1; i++, j++) 
        {
            twoArr[i] = (&data)[j];
        }
        OptMergeSort(*oneArr, halfsize);
        OptMergeSort(*twoArr, halfsize);
        OptimizedMerge(halfsize, size - (halfsize), *oneArr, *twoArr, data);
        delete oneArr;
        delete twoArr;
    }
}
void __fastcall OptimizedMerge(int sizeOfLeft, int sizeOfRight, int& left, int& right, int& result )
{
    int leftCounter = 0;
    int rightCounter = 0;
    int mergeCounter = 0;
    // merge the two arrays
    while ((leftCounter < sizeOfLeft) && (rightCounter < sizeOfRight))
    {
        if((&left)[leftCounter] <= (&right)[rightCounter])
        {
            (&result)[mergeCounter] = (&right)[rightCounter];
            ++rightCounter;
        }
        else
        {
            (&result)[mergeCounter] = (&left)[leftCounter];
            ++leftCounter;
        }
        ++mergeCounter;
    }

    // handle the left-overs

    // if the entire left was used, then we have left-overs from the right to copy over
    if(leftCounter == sizeOfLeft)
    {
        // copy the right to the result
        while(rightCounter < sizeOfRight)
        {
            (&result)[mergeCounter] = (&right)[rightCounter];
            ++mergeCounter;
            ++rightCounter;
        }        
    }
    else
    {
        // copy the left to the result
        while(leftCounter < sizeOfLeft)
        {
            (&result)[mergeCounter] = (&left)[leftCounter];
            ++mergeCounter;
            ++leftCounter;
        }
    }
}